package linklist;

import lombok.extern.slf4j.Slf4j;

/**
 * created with IDEA
 *
 * @author haifeng.wang
 * @since 2019-06-19-10:40
 */
@Slf4j
public class LinkedList<E> {

    private Node<E> head;
    private int size = 0;

    public LinkedList() {
            head = new Node<>(null);
    }

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        log.info("list.getHeader():{]", list.getHead());
        Integer add = list.add(2);
        log.info("add:{}", add);
        log.info("list.getSize():{}", list.getSize());
        try {
            list.add(new Node<Integer>(3), 2);
        } catch (Exception e) {
            log.error("add failed.");
        }
        log.info("list:{}", list);
        log.info("list.getTail():{}", list.getTail().data);

        //删除
       /* try {
            list.delete(1);
        } catch (Exception e) {
            log.error("delete failed.");
        }*/
        Node<Integer> node = new Node<Integer>(1);
        list.delete(node);

        log.info("list:{}", list);
    }

    public int getSize() {
        return size;
    }

    public Node<E> getHead() {
        return head;
    }

    public Node<E> getTail() {
        Node<E> current = head;
        while (null != current.next) {
            current = current.next;
        }
        return current;
    }

    /**
     * 默认添加到元素末尾
     *
     * @param node 待添加的节点
     * @return 被添加的节点
     */
    public Node<E> add(Node<E> node) {
        if (null == head.data) {
            head = node;
            ++size;
            return node;
        }
        Node<E> current = head;
        while (null != head.next) {
            current = current.next;
        }
        current.next = node;
        ++size;
        return node;
    }

    /**
     * 默认添加到元素末尾
     *
     * @param data 待添加的元素
     * @return 被添加的元素
     */
    public E add(E data) {
        add(new Node<E>(data));
        return data;
    }

    /**
     * 将节点添加到指定位置
     *
     * @param node  被添加的节点
     * @param index 位置索引
     * @return 被添加的节点
     */
    public Node<E> add(Node<E> node, int index) throws Exception {
        if (index > size || index < 0) {
            throw new Exception("");
        }
        //从头部添加，头部没有前缀节点
        if (index == 0) {
            node.next = head;
            ++size;
            return node;
        }
        //既有前缀又可能有后缀
        Node<E> current = head;
        for (int i = 1; i < index - 1; i++) {
            current = current.next;
        }
        Node<E> temp = current.next;
        current.next = node;
        //将后一个节点设置为被添加节点的next节点
        node.next = temp;
        ++size;
        return node;
    }

    /**
     * 删除指定数据，删除后将后一个节点设置为前一个节点的后缀接点
     * 思路：将链表分成两部分，其中后一部分的head 是待删除的节点
     *
     * @param node
     */
    public void delete(Node<E> node) {
        //如果正好是头节点
        if (head.data == node.data) {
            Node<E> tmp = head.next;
            head.next = null;
            head = tmp;
            size--;
            return;
        }
        //删除的基本逻辑就是将当前过滤掉：例如 A B C，直接将A与C相连
        Node<E> current = head;
        for (int i = 0; i < size; i++) {
            Node<E> tmp = current;
            // current 是被比较/过滤对象
            current = current.next;
            if (current.data == node.data) {
                // 直接跳过 current ，从 current 前缀跳到current后缀
                tmp.next = current.next;
                size--;
                break;
            }
        }
    }

    /**
     * 删除,从位置1~size
     *
     * @param index
     * @throws Exception
     */
    public void delete(int index) throws Exception {
        if (index > size || index < 0) {
            throw new Exception("");
        }

        Node<E> current = head;
        for (int i = 1; i < index; i++) {
            current = current.next;
        }
        Node<E> tmp = current.next;
        current.next = tmp.next;
        tmp.next = null;
        size--;
    }

    /**
     * 删除链表中的重复元素(外循环 + 内循环)
     */
    public void removeDuplicateNodes() {
        Node<E> current = head;
        while (null != current) {
            Node<E> tmp = current;
            while (null != tmp && null != tmp.next) {
                if (tmp.next.data.equals(current.data)) {
                    Node<E> duplicateNode = tmp.next;
                    tmp.next = duplicateNode.next;
                    duplicateNode.next = null;
                    size--;
                }
                tmp = tmp.next;
            }
            current = current.next;
        }
    }

    /**
     * 找出单链表中倒数第K个元素(双指针法, 相差K - 1步)
     *
     * @param k
     * @return
     */
    public Node<E> getEndK(int k) {
        Node<E> pre = head.next;
        Node<E> post = head.next;
        for (int i = 0; i < k; i++) {
            // pre先走k-1步，当pre走到链表末端时，post正好指向倒数第K个节点
            if (null != pre && null != pre.next) {
                pre = pre.next;
            }
        }

        while (null != pre && null != pre.next) {
            pre = pre.next;
            post = post.next;
        }
        return post;
    }

}
